package com.剑指offer.第四章;

/**
 * 三种办法：
 * 1、将其中一个链表的尾节点的next 设置头节点 这样就成为了一个环形链表。使用找出环形链表的入口节点的解法进行求解
 * 2、遍历两条链表的所有节点，两个栈存储每次遍历的节点，之后每次取出栈顶的元素，当最后一个相同的节点就是第一个重合的节点。
 * 3、先求出每个链表的长度，然后计算长的比短的多了n个节点，就先让p1 走n步，然后在一起出发，当相同时，就是第一个重合的节点。
 */
public class 两个链表的第1个重合节点 {


    /**
     * 3、先求出每个链表的长度，然后计算长的比短的多了n个节点，就先让p1 走n步，然后在一起出发，当相同时，就是第一个重合的节点。
     * @return
     */
    public static ListNode resolve(ListNode headA, ListNode headB) {
        int count1 = count(headA);
        int count2 = count(headB);

        int del = Math.abs(count1 - count2);
        // 比较长度 找出长，短链表
        ListNode longer = count1 > count2 ? headA : headB;
        ListNode shorter = count1 > count2 ? headB : headA;
        // 先让长的走del步
        ListNode node1 = longer;
        for (int i = 0; i < del; i++) {
            node1 = node1.next;
        }

        ListNode node2 = shorter;
        while (node1 != node2) {
            node1 = node1.next;
            node2 = node2.next;
        }
        return node1;
    }

    public static int count(ListNode head) {
        int count = 0;
        while (head != null) {
            count++;
            head = head.next;
        }
        return count;
    }

    public static void main(String[] args) {

    }

}
